package gameoflife.cluster;

import gameoflife.Cell;
import gameoflife.ChangeListener;
import gameoflife.Position;
import gameoflife.automaton.Automaton;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.SortedSet;
import java.util.TreeSet;

public class Clusterer {
	private Automaton automaton;
	private List<SortedSet<Position>> clusters = new ArrayList<SortedSet<Position>>();

	public Clusterer(final Automaton automaton) {
		this.automaton = automaton;
		cluster();
		automaton.addChangeListener(new ChangeListener() {
			@Override
			public void stateChanged(int changecode) {
				cluster();
			}
		});
	}

	public List<SortedSet<Position>> getClusters() {
		return clusters;
	}

	private static class CellAt {
		public Position position;
		public Range at;
		public CellAt(Position position, Range at) {
			this.position = position;
			this.at = at;
		}
	}

	public void cluster() {
		clusters.clear();
		final Map<Position, SortedSet<Position>> map = new HashMap<Position, SortedSet<Position>>();

		automaton.accept(new Automaton.Visitor() {
			@Override
			public void visit(Cell cell) {
				map.put(cell, null);
			}
		});

		for (Position p : new ArrayList<Position>(map.keySet())) {
			if (map.get(p) == null) {
				SortedSet<Position> newCluster = new TreeSet<Position>();
				map.put(p, newCluster);
				newCluster.add(p);

				Queue<CellAt> queue = new LinkedList<CellAt>();
				queue.add(new CellAt(p, null));

				while (!queue.isEmpty()) {
					CellAt head = queue.poll();

					for (Range dir : head.at == null ? Range.ALL : head.at.reachable) {
						Position neighbor = new Position(head.position.getX() + dir.x, head.position.getY() + dir.y);

						if (map.containsKey(neighbor) && map.get(neighbor) == null) {
							queue.add(new CellAt(neighbor, dir));
							map.put(neighbor, newCluster);
							newCluster.add(neighbor);
						}
					}
				}
				clusters.add(newCluster);
			}
		}
	}

}
